package zw_1_100.zw_20_有效的括号;

import java.util.*;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 * <p>
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 * <p>
 * 输入：s = "([)]"
 * 输出：false
 * 示例 5：
 * <p>
 * 输入：s = "{[]}"
 * 输出：true
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 104
 * s 仅由括号 '()[]{}' 组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


class Solution {

    public static void main(String[] args) {
        String s = "([{})]";
        boolean b = isValid(s);
        System.out.println(b);
    }


    /**
     * stack,可以不使用map
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        return stack.empty();
    }
    /**
     * stack + map
      */
//    private static final Map<Character, Character> map = new HashMap<Character, Character>() {{
//        put('{', '}');
//        put('[', ']');
//        put('(', ')');
//        put('?', '?');
//    }};
//    public static boolean isValid(String s) {
//        if (s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
//        LinkedList<Character> stack = new LinkedList<Character>() {{
//            add('?');
//        }};
//        for (Character c : s.toCharArray()) {
//            if (map.containsKey(c)) stack.addLast(c);
//            else if (map.get(stack.removeLast()) != c) return false;
//        }
//        return stack.size() == 1;
//    }


//    public static boolean isValid(String s) {
//        HashMap<Character, Character> map = new HashMap<Character, Character>() {{
//            put('(', ')');
//            put('[', ']');
//            put('{', '}');
//        }};
//
//        Deque<Character> queue = new LinkedList<>();
//        for (char c : s.toCharArray()) {
//            if (map.containsKey(c)) {//如果为左括号,入栈
//                queue.addFirst(c);
//            } else {//此时为右括号
//                if (!queue.isEmpty()) {
//                    if (map.get(queue.poll()) != c) {
//                        return false;//如果栈顶弹出的括号和此时的c不匹配直接返回false
//                    }
//                } else {//此时栈为空,但却来了个右括号,也直接返回false
//                    return false;
//                }
//            }
//        }
//        //循环结束时,栈为空,就为有效括号
//        return queue.isEmpty();
//    }

}
